from typing import List


class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        n = len(days)
        inf = float('inf')
        dp = [[inf for _ in range(6)] for _ in range(n)]
        dp[0][0] = costs[0]
        dp[0][1] = costs[0]
        dp[0][2] = costs[1]
        dp[0][3] = costs[1]
        dp[0][4] = costs[2]
        dp[0][5] = costs[2]

        for i in range(1, n):
            dp[i][0] = min(dp[i - 1]) + costs[0]
            dp[i][2] = min(dp[i - 1]) + costs[1]
            dp[i][4] = min(dp[i - 1]) + costs[2]
            for j in range(i - 1, -1, -1):
                if days[i] - days[j] < 1:
                    dp[i][1] = min(dp[i][1], dp[j][0])
                if days[i] - days[j] < 7:
                    dp[i][3] = min(dp[i][3], dp[j][2])
                if days[i] - days[j] < 30:
                    dp[i][5] = min(dp[i][5], dp[j][4])
        return min(dp[-1])


if __name__ == '__main__':
    s = Solution()
    r = s.mincostTickets(days=[1, 4, 6, 7, 8, 20], costs=[2, 7, 15])
    print(r)
